1. Field of the Invention
The present invention relates to a key telephone system, and in particular, to a method for reducing a search time of a database to quickly set a least cost route.
2. Description of the Related Art
A key telephone system commonly employs a technique for reducing the communication cost, such as a least cost route (hereinafter, referred to as "LCR"). In order to perform the LCR function, a database should be built upon a close examination of traffic intensity and the communication networks surrounding the operating site. In general, however, it takes a long time to search the LCR-related database, which results into a deterioration of the system performance. Hence, there is proposed a binary search method for sorting all records in advance when building the database, to reduce a search time of the database. However, in case of an overload due to heavy traffic, the binary searching also takes a long search time, which causes a hinderance to a real-time service. Accordingly, there is a demand for developing an advanced searching algorithm.
Out of the LCR-related databases, a DCT (Digit Comparison Table) database (which is a sort of a buffer table into which dialed digits are piled up) is most closely related to the search time of the database. The DCT database has hundreds of numerical strings programmed therein. A delay of the search time has a great influence particularly on the performance of a system which manages the calls using a main processor only, without a separate signal processor. The key telephone system employs a table search method consisting of an insertion sort algorithm and the binary search algorithm, to reduce the search time. The insertion sort algorithm is used to build the database, and is the most simple one of the known sort algorithms. The insertion sort algorithm compares the records in sequence from the beginning to search an exact position of the records, so as to register a new record into the DCT database or delete the pre-registered records. The binary search algorithm builds an index table having key values corresponding to the respective records, and compares a record K with a key value Ki at the middle of the table. In such a case, the following three conditions will occur.
1) K&lt;Ki [Ri, Ri+1, . . . Rn are the records excepted from the search] PA1 2) K=Ki [Search Completion] PA1 3) K&gt;Ki [R1, R2, . . . Ri are the record excepted from the search]
In this manner, the searching is repeated until a desired record is searched. The number of the comparisons is evaluated based on log.sub.2 N, where N represents the number of records.
A medium to large sized key telephone system having the LCR function has a system monitoring cycle of about 100 msec. In case of heavy traffic, the system may be overloaded because it takes a long time to manage a great number of calls. Thus, the system may operate undesirably at low speed, lowering the system performance. Here, the increased search time results into an extension of the system monitoring cycle, thereby causing a deterioration of the system performance. When a frequently accessed record (i.e., a record with a higher access frequency) is located at a place of the digit comparison table where the record can be searched by many searching times, the searching for this record has a great influence on the system performance. If the time required for searching 500 records by the binary searching is Tms, the search time for the corresponding record is about 9.times.Tms, and the search time continues to influence the system as long as the place of the DCT record is not changed. This is because the records with a very low access frequency are all included in the index table, maintaining the constant record number N. Thus, the key telephone system undesirably compares the unnecessary records with the lower access is frequency, increasing the search time. A switching system managing the calls in a time-sharing basis has an overhead of 9Tms for every call management operation. If 30 subscribers attempt to make calls simultaneously, the whole system monitoring cycle increases up to 30.times.9 Tms. Thus, the subscriber who is allocated finally is serviceable after a time delay of (monitoring cycle)+(30-1).times.9 Tms. If Tms=2 ms, the overhead time becomes 29.times.18 ms=522 ms, and the service is delayed by the overhead time of 522 ms, which results into a deterioration of the system performance. Such an overhead problem can not be solved by the conventional binary searching method.
Examples of uses of least cost routing systems are further described in: U.S. Pat. No. 4,410,765 to Alfred M. Hestad et al. entitled Telephone Call Routing And Charging System; U.S. Pat. No. 5,425,085 to Gerald J. Weinberger et al. entitled Least Cost Routing Device For Separate Connection Into Phone Line; U.S. Pat. No. 5,452,351 to Keiji Yamamoto entitled Electronic Private Branch Exchange Having An LCR Function And A Method Of Accessing A Particular Common Carrier In That Exchange; and U.S. Pat. No. 5,638,433 to Walter J. Bubien, Jr. et al. entitled Best Rate Telecommunication Access Code And Data Transceiver/Facilitator (BRFT).